#include <iostream>
#include <memory>
#include <exception>

/* 
    Example Usage:
    g++ -Wall -o myout expression.cpp
    ./myout
*/

/*
  Basic Idea:
  I build up an expression tree, where each Node in the tree contains an auto_ptr to an Operator and
  auto_ptrs to the left and right children nodes (null if child doesn't exist).  When the root of the tree
  goes out of scope, the memory for the entire tree is released.  If I make a tree the subtree of 
  another tree, that subtree no longer has control of the Operators and can not be used in other expressions.
  See main for more details.
 */

class multieval : public std::exception
{
public:
  virtual const char* what() const throw(){
    return "Each expression may only be evaluated once.";
  }
} meval;

class Operator {
public:
  virtual int eval() const = 0;
  virtual ~Operator(){}
};

class Constant : public Operator {
public:
  Constant(int a) : a_(a) {
    printf("Creating constant %zu\n", (size_t)this);
  }
  ~Constant(){
    printf("Deleting constant %zu\n", (size_t)this);
  }
  int eval() const{
    return a_;
  }
private:
  int a_;
};

class Negate : public Operator {
public:
  Negate(const Operator & op) : op_(op) {
    printf("Creating negate %zu\n", (size_t)this);
  }
  ~Negate(){
    printf("Deleting negate %zu\n", (size_t)this);
  }
  int eval() const{
    return -1*op_.eval();
  }
private:
  const Operator & op_;
};

class Add : public Operator {
public:
  Add(const Operator & a, const Operator & b) : a_(a), b_(b) {
    printf("Creating add %zu\n", (size_t)this); 
  }
  ~Add(){
    printf("Deleting add %zu\n", (size_t)this);
  }
  int eval() const{
    return (a_.eval() + b_.eval());
  }
private:
  const Operator & a_;
  const Operator & b_;
}; 

class Node {
public:
  Node(Operator * i) : iter(i), left_child(0), right_child(0) {
    //printf("Creating NODE %zu\n", (size_t)this);
  }
  Node(Operator * i, std::auto_ptr<Node> n) 
    : iter(i), left_child(n), right_child(0) {
    //printf("Creating NODE %zu\n", (size_t)this);
    n.reset(0);
  }
  Node(Operator * i, std::auto_ptr<Node> n, std::auto_ptr<Node> m) 
    : iter(i), left_child(n), right_child(m){
    //printf("Creating NODE %zu\n", (size_t)this);
    n.reset(0);
    m.reset(0);
  }
  ~Node(){
    //printf("Deleting NODE %zu\n", (size_t)this);
  }

  int eval() const {
    return iter->eval();
  }

  std::auto_ptr<Operator> iter;
  
private:
  std::auto_ptr<Node> left_child;
  std::auto_ptr<Node> right_child;
};

std::auto_ptr<Node> constant(int a){
  return std::auto_ptr<Node>(new Node(new Constant(a)));
}

std::auto_ptr<Node> neg(std::auto_ptr<Node>  a){
  if(!a.get()) throw meval;
  return std::auto_ptr<Node>(new Node(new Negate(*(a->iter)), a));
}

std::auto_ptr<Node> add(std::auto_ptr<Node>  a, std::auto_ptr<Node>  b){
  if(!a.get()) throw meval;
  if(!b.get()) throw meval;
  return std::auto_ptr<Node>(new Node(new Add(*(a->iter),*(b->iter)), a, b));
}

int add1(int a){
  return add(constant(a), constant(1))->eval();
}

using namespace std;
int main(){
  //I can do this with no problem . . .
  printf("Test 1\n\n");
  {
    Constant a(3);
    Constant b(4);
    Negate c(b);
    Add d(a, c);
    printf("%d\n", d.eval());
  }
  printf("\n");
  
  //But I really want to be able to chain operators together, such as
  // add(constant(3), neg(constant(4))).eval()
  //I can't create a function that returns an Operator, because the Operator class is abstract.
  //If I return a reference to an Operator, the Operator created inside the function will go out of scope.

  //Here is the syntax for the auto_ptr solution
  printf("Test 2\n\n");
  {
    printf("%d\n", add(constant(3), neg(constant(4)))->eval());
  }
  printf("\n");

  //Do not allow an operation to be used twice in one expression or in another expression
  
  printf("Test 3\n\n");
  try {
    //This should be fine, a is only used once.
    auto_ptr<Node> a = constant(1);
    printf("%d\n", add(constant(1), a)->eval());
  }catch(exception& e){                                                               
    cout << e.what() << endl;                                                    
  }
  printf("\n");

  printf("Test 4\n");
  try {
    //Using same node multiple times in an expression is not allowed
    auto_ptr<Node> a = constant(1);
    printf("%d\n", add(a, a)->eval());
  }catch(exception& e){                                                               
    cout << e.what() << endl;                                                    
  }
  printf("\n");

  printf("Test 5\n");
  try {
    //Re-using a node in another expression is not allowed
    auto_ptr<Node> a = constant(1);
    printf("%d\n", add(constant(1), a)->eval());
    printf("%d\n", add(constant(1), a)->eval());
  }catch(exception& e){                                                               
    cout << e.what() << endl;                                                    
  }
  printf("\n");

  printf("Test 6\n");
  //Creating helper routines . . .
  printf("%d\n", add1(14));
  printf("%d\n", add1(15));
  printf("%d\n", add1(add1(14)));
  printf("\n");

  return 0;
}
